home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Mac Game Programming Gurus / TricksOfTheMacGameProgrammingGurus.iso / CodeWarrior Lite / Metrowerks C⁄C++ Lite / Headers / STL Headers / list.h < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-06  |  12.6 KB  |  466 lines  |  [TEXT/MMCC]
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  */
  15.  
  16. #ifndef LIST_H
  17. #define LIST_H
  18.  
  19. #include <function.h>
  20. #include <algobase.h>
  21. #include <iterator.h>
  22. #include <bool.h>
  23.     
  24. #ifndef Allocator
  25. #define Allocator allocator
  26. #include <defalloc.h>
  27. #endif
  28.  
  29. #ifndef list 
  30. #define list list
  31. #endif
  32.  
  33. template <class T>
  34. class list {
  35. protected:
  36.     typedef Allocator<void>::pointer void_pointer;
  37.     struct list_node;
  38.     friend list_node;
  39.     struct list_node {
  40.     void_pointer next;
  41.     void_pointer prev;
  42.     T data;
  43.     };
  44.     static Allocator<list_node> list_node_allocator;
  45.     static Allocator<T> value_allocator;
  46. public:      
  47.     typedef T value_type;
  48.     typedef Allocator<T> value_allocator_type;
  49.     typedef Allocator<T>::pointer pointer;
  50.     typedef Allocator<T>::reference reference;
  51.     typedef Allocator<T>::const_reference const_reference;
  52.     typedef Allocator<list_node> list_node_allocator_type;
  53.     typedef Allocator<list_node>::pointer link_type;
  54.     typedef Allocator<list_node>::size_type size_type;
  55.     typedef Allocator<list_node>::difference_type difference_type;
  56. protected:
  57.     size_type buffer_size() {
  58.     return list_node_allocator.init_page_size();
  59.     }
  60.     struct list_node_buffer;
  61.     friend list_node_buffer;
  62.     struct list_node_buffer {
  63.     void_pointer next_buffer;
  64.     link_type buffer;
  65.     };
  66. public:
  67.     typedef Allocator<list_node_buffer> buffer_allocator_type;
  68.     typedef Allocator<list_node_buffer>::pointer buffer_pointer;     
  69. protected:
  70.     static Allocator<list_node_buffer> buffer_allocator;
  71.     static buffer_pointer buffer_list;
  72.     static link_type free_list;
  73.     static link_type next_avail;
  74.     static link_type last;
  75.     void add_new_buffer() {
  76.     buffer_pointer tmp = buffer_allocator.allocate((size_type)1);
  77.     tmp->buffer = list_node_allocator.allocate(buffer_size());
  78.     tmp->next_buffer = buffer_list;
  79.     buffer_list = tmp;
  80.     next_avail = buffer_list->buffer;
  81.     last = next_avail + buffer_size();
  82.     }
  83.     static size_type number_of_lists;
  84.     void deallocate_buffers();
  85.     link_type get_node() {
  86.     link_type tmp = free_list;
  87.     return free_list ? (free_list = (link_type)(free_list->next), tmp) 
  88.         : (next_avail == last ? (add_new_buffer(), next_avail++) 
  89.         : next_avail++);
  90.     // ugly code for inlining - avoids multiple returns
  91.     }
  92.     void put_node(link_type p) {
  93.     p->next = free_list;
  94.     free_list = p;
  95.     }
  96.  
  97. protected:
  98.     link_type node;
  99.     size_type length;
  100. public:
  101.     class iterator;
  102.     class const_iterator;
  103.     class iterator : public bidirectional_iterator<T, difference_type> {
  104.     friend class list<T>;
  105.     friend class const_iterator;
  106. //  friend bool operator==(const iterator& x, const iterator& y);
  107.     protected:
  108.     link_type node;
  109.     iterator(link_type x) : node(x) {}
  110.     public:
  111.     iterator() {}
  112.     bool operator==(const iterator& x) const { return node == x.node; }
  113.     reference operator*() const { return (*node).data; }
  114.     iterator& operator++() { 
  115.         node = (link_type)((*node).next);
  116.         return *this;
  117.     }
  118.     iterator operator++(int) { 
  119.         iterator tmp = *this;
  120.         ++*this;
  121.         return tmp;
  122.     }
  123.     iterator& operator--() { 
  124.         node = (link_type)((*node).prev);
  125.         return *this;
  126.     }
  127.     iterator operator--(int) { 
  128.         iterator tmp = *this;
  129.         --*this;
  130.         return tmp;
  131.     }
  132.     };
  133.     class const_iterator : public bidirectional_iterator<T, difference_type> {
  134.     friend class list<T>;
  135.     protected:
  136.     link_type node;
  137.     const_iterator(link_type x) : node(x) {}
  138.     public:     
  139.     const_iterator() {}
  140.     const_iterator(const iterator& x) : node(x.node) {}
  141.     bool operator==(const const_iterator& x) const { return node == x.node; } 
  142.     const_reference operator*() const { return (*node).data; }
  143.     const_iterator& operator++() { 
  144.         node = (link_type)((*node).next);
  145.         return *this;
  146.     }
  147.     const_iterator operator++(int) { 
  148.         const_iterator tmp = *this;
  149.         ++*this;
  150.         return tmp;
  151.     }
  152.     const_iterator& operator--() { 
  153.         node = (link_type)((*node).prev);
  154.         return *this;
  155.     }
  156.     const_iterator operator--(int) { 
  157.         const_iterator tmp = *this;
  158.         --*this;
  159.         return tmp;
  160.     }
  161.     };
  162.     typedef reverse_bidirectional_iterator<const_iterator, value_type,
  163.                                            const_reference, difference_type>
  164.     const_reverse_iterator;
  165.     typedef reverse_bidirectional_iterator<iterator, value_type, reference,
  166.                                            difference_type>
  167.         reverse_iterator; 
  168.     list() : length(0) {
  169.     ++number_of_lists;
  170.     node = get_node();
  171.     (*node).next = node;
  172.     (*node).prev = node;
  173.     }
  174.     iterator begin() { return (link_type)((*node).next); }
  175.     const_iterator begin() const { return (link_type)((*node).next); }
  176.     iterator end() { return node; }
  177.     const_iterator end() const { return node; }
  178.     reverse_iterator rbegin() { return reverse_iterator(end()); }
  179.     const_reverse_iterator rbegin() const { 
  180.         return const_reverse_iterator(end()); 
  181.     }
  182.     reverse_iterator rend() { return reverse_iterator(begin()); }
  183.     const_reverse_iterator rend() const { 
  184.         return const_reverse_iterator(begin());
  185.     } 
  186.     bool empty() const { return length == 0; }
  187.     size_type size() const { return length; }
  188.     size_type max_size() const { return list_node_allocator.max_size(); }
  189.     reference front() { return *begin(); }
  190.     const_reference front() const { return *begin(); }
  191.     reference back() { return *(--end()); }
  192.     const_reference back() const { return *(--end()); }
  193.     void swap(list<T>& x) {
  194.     ::swap(node, x.node);
  195.     ::swap(length, x.length);
  196.     }
  197.     iterator insert(iterator position, const T& x) {
  198.     link_type tmp = get_node();
  199.     construct(value_allocator.address((*tmp).data), x);
  200.     (*tmp).next = position.node;
  201.     (*tmp).prev = (*position.node).prev;
  202.     (*(link_type((*position.node).prev))).next = tmp;
  203.     (*position.node).prev = tmp;
  204.     ++length;
  205.     return tmp;
  206.     }
  207.     void insert(iterator position, const T* first, const T* last);
  208.     void insert(iterator position, const_iterator first,
  209.         const_iterator last);
  210.     void insert(iterator position, size_type n, const T& x);
  211.     void push_front(const T& x) { insert(begin(), x); }
  212.     void push_back(const T& x) { insert(end(), x); }
  213.     void erase(iterator position) {
  214.     (*(link_type((*position.node).prev))).next = (*position.node).next;
  215.     (*(link_type((*position.node).next))).prev = (*position.node).prev;
  216.     destroy(value_allocator.address((*position.node).data));
  217.     put_node(position.node);
  218.     --length;
  219.     }
  220.     void erase(iterator first, iterator last);
  221.     void pop_front() { erase(begin()); }
  222.     void pop_back() { 
  223.     iterator tmp = end();
  224.     erase(--tmp);
  225.     }
  226.     list(size_type n, const T& value = T()) : length(0) {
  227.     ++number_of_lists;
  228.     node = get_node();
  229.     (*node).next = node;
  230.     (*node).prev = node;
  231.     insert(begin(), n, value);
  232.     }
  233.     list(const T* first, const T* last) : length(0) {
  234.     ++number_of_lists;
  235.     node = get_node();
  236.     (*node).next = node;
  237.     (*node).prev = node;
  238.     insert(begin(), first, last);
  239.     }
  240.     list(const list<T>& x) : length(0) {
  241.     ++number_of_lists;
  242.     node = get_node();
  243.     (*node).next = node;
  244.     (*node).prev = node;
  245.     insert(begin(), x.begin(), x.end());
  246.     }
  247.     ~list() {
  248.     erase(begin(), end());
  249.     put_node(node);
  250.     if (--number_of_lists == 0) deallocate_buffers();
  251.     }
  252.     list<T>& operator=(const list<T>& x);
  253. protected:
  254.     void transfer(iterator position, iterator first, iterator last) {
  255.     (*(link_type((*last.node).prev))).next = position.node;
  256.     (*(link_type((*first.node).prev))).next = last.node;
  257.     (*(link_type((*position.node).prev))).next = first.node;  
  258.     link_type tmp = link_type((*position.node).prev);
  259.     (*position.node).prev = (*last.node).prev;
  260.     (*last.node).prev = (*first.node).prev; 
  261.     (*first.node).prev = tmp;
  262.     }
  263. public:
  264.     void splice(iterator position, list<T>& x) {
  265.     if (!x.empty()) {
  266.         transfer(position, x.begin(), x.end());
  267.         length += x.length;
  268.         x.length = 0;
  269.     }
  270.     }
  271.     void splice(iterator position, list<T>& x, iterator i) {
  272.     iterator j = i;
  273.     if (position == i || position == ++j) return;
  274.     transfer(position, i, j);
  275.     ++length;
  276.     --x.length;
  277.     }
  278.     void splice(iterator position, list<T>& x, iterator first, iterator last) {
  279.     if (first != last) {
  280.         if (&x != this) {
  281.         difference_type n = 0;
  282.             distance(first, last, n);
  283.             x.length -= n;
  284.             length += n;
  285.         }
  286.         transfer(position, first, last);
  287.     }
  288.     }
  289.     void remove(const T& value);
  290.     void unique();
  291.     void merge(list<T>& x);
  292.     void reverse();
  293.     void sort();
  294. };
  295.  
  296. template <class T>
  297. list<T>::buffer_pointer list<T>::buffer_list = 0;
  298.  
  299. template <class T>
  300. list<T>::link_type list<T>::free_list = 0;
  301.  
  302. template <class T>
  303. list<T>::link_type list<T>::next_avail = 0;
  304.  
  305. template <class T>
  306. list<T>::link_type list<T>::last = 0;
  307.  
  308. template <class T>
  309. list<T>::size_type list<T>::number_of_lists = 0;
  310.  
  311. template <class T>
  312. list<T>::list_node_allocator_type list<T>::list_node_allocator;
  313.  
  314. template <class T>
  315. list<T>::value_allocator_type list<T>::value_allocator;
  316.  
  317. template <class T>
  318. list<T>::buffer_allocator_type list<T>::buffer_allocator;
  319.  
  320. /* 
  321.  * currently the following does not work - made into a member function
  322.  
  323. template <class T>
  324. inline bool operator==(const list<T>::iterator& x, const list<T>::iterator& y) { 
  325.     return x.node == y.node; 
  326. }
  327. */
  328.  
  329. template <class T>
  330. inline bool operator==(const list<T>& x, const list<T>& y) {
  331.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  332. }
  333.  
  334. template <class T>
  335. inline bool operator<(const list<T>& x, const list<T>& y) {
  336.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  337. }
  338.  
  339. template <class T>
  340. void list<T>::deallocate_buffers() {
  341.     while (buffer_list) {
  342.     buffer_pointer tmp = buffer_list;
  343.     buffer_list = (buffer_pointer)(buffer_list->next_buffer);
  344.     list_node_allocator.deallocate(tmp->buffer);
  345.     buffer_allocator.deallocate(tmp);
  346.     }
  347.     free_list = 0;
  348.     next_avail = 0;
  349.     last = 0;
  350. }
  351.  
  352. template <class T>
  353. void list<T>::insert(iterator position, const T* first, const T* last) {
  354.     while (first != last) insert(position, *first++);
  355. }
  356.      
  357. template <class T>
  358. void list<T>::insert(iterator position, const_iterator first,
  359.              const_iterator last) {
  360.     while (first != last) insert(position, *first++);
  361. }
  362.  
  363. template <class T>
  364. void list<T>::insert(iterator position, size_type n, const T& x) {
  365.     while (n--) insert(position, x);
  366. }
  367.  
  368. template <class T>
  369. void list<T>::erase(iterator first, iterator last) {
  370.     while (first != last) erase(first++);
  371. }
  372.  
  373. template <class T>
  374. list<T>& list<T>::operator=(const list<T>& x) {
  375.     if (this != &x) {
  376.     iterator first1 = begin();
  377.     iterator last1 = end();
  378.     const_iterator first2 = x.begin();
  379.     const_iterator last2 = x.end();
  380.     while (first1 != last1 && first2 != last2) *first1++ = *first2++;
  381.     if (first2 == last2)
  382.         erase(first1, last1);
  383.     else
  384.         insert(last1, first2, last2);
  385.     }
  386.     return *this;
  387. }
  388.  
  389. template <class T>
  390. void list<T>::remove(const T& value) {
  391.     iterator first = begin();
  392.     iterator last = end();
  393.     while (first != last) {
  394.     iterator next = first;
  395.     ++next;
  396.     if (*first == value) erase(first);
  397.     first = next;
  398.     }
  399. }
  400.  
  401. template <class T>
  402. void list<T>::unique() {
  403.     iterator first = begin();
  404.     iterator last = end();
  405.     if (first == last) return;
  406.     iterator next = first;
  407.     while (++next != last) {
  408.     if (*first == *next)
  409.         erase(next);
  410.     else
  411.         first = next;
  412.     next = first;
  413.     }
  414. }
  415.  
  416. template <class T>
  417. void list<T>::merge(list<T>& x) {
  418.     iterator first1 = begin();
  419.     iterator last1 = end();
  420.     iterator first2 = x.begin();
  421.     iterator last2 = x.end();
  422.     while (first1 != last1 && first2 != last2)
  423.     if (*first2 < *first1) {
  424.         iterator next = first2;
  425.         transfer(first1, first2, ++next);
  426.         first2 = next;
  427.     } else
  428.         ++first1;
  429.     if (first2 != last2) transfer(last1, first2, last2);
  430.     length += x.length;
  431.     x.length= 0;
  432. }
  433.  
  434. template <class T>
  435. void list<T>::reverse() {
  436.     if (size() < 2) return;
  437.     for (iterator first = ++begin(); first != end();) {
  438.     iterator old = first++;
  439.     transfer(begin(), old, first);
  440.     }
  441. }    
  442.  
  443. template <class T>
  444. void list<T>::sort() {
  445.     if (size() < 2) return;
  446.     list<T> carry;
  447.     list<T> counter[64];
  448.     int fill = 0;
  449.     while (!empty()) {
  450.     carry.splice(carry.begin(), *this, begin());
  451.     int i = 0;
  452.     while(i < fill && !counter[i].empty()) {
  453.         counter[i].merge(carry);
  454.         carry.swap(counter[i++]);
  455.     }
  456.     carry.swap(counter[i]);         
  457.     if (i == fill) ++fill;
  458.     } 
  459.     while(fill--) merge(counter[fill]);
  460. }
  461.  
  462. #undef Allocator
  463. #undef list
  464.  
  465. #endif
  466.